关于微信公众号

首先声明，这个系列所分享的“好题” 仅代表我个人在解这道题时可能觉得这道题某一个知识点很有趣；或是很新颖；或是出题人对这道题各个知识点的衔接处理的很好，而不是单纯套娃；或是看了出题人的题解觉得特别优雅，或是觉得自己的解法很妙…… 但并不保证这道题目的实时性、原创性，可能我看到这道题的时候它已经是被抄袭过的，但我并没有遇到过原题。 （题好，但不对比赛给予评价）另外为了避免纯粹的拿来主义，以给读者一定的思考、操作空间，这个系列也不会直接给出完整的解题 exp，大家自己也多试试叭！

今天这道题目来自 2023 网信柏鹭杯 - fractRSA

题目内容

#python3
import sys 
sys.path.append("..") 
from Crypto.Util.number import *
from random import *
from sage.all import *
from  secret import flag1 as flag

num1 = 3
num2 = 5
while(num1<num2):
    num1 = getPrime(512)
    num2 = getPrime(512)
pt = bytes_to_long(flag) + num2

ring = RealField(1100)
num3 = ring(num1) / ring(num2)
print("num3 = ", num3)

while True:
    p = randint(2**511, num1)
    q = randint(2**511, num2)
    if isPrime(p) and isPrime(q) and p!=q:
        break
 
N = p*q
e = 65537
leak = pow(p-q, num1, num1*num2)
ct = pow(pt, e, N)

print("ct = ", ct)
print("N = ", N)
print("leak = ", leak)

"""
num3 = 1.23389923415003373900567515471436168841941584796842188964423737295914869304653496800649965063081353720701415762591488370228399019899893688681309320356016722276295236528757306976510687729729934668311830828756908988350841843676900575414367123810470585198055372776278588638204471298838884740198056387082949710435502826460830711429956
ct = 31011170589632318837149853165664224847925206003567781692767655474759523146503572164952138829336342836023903919700264739071138739105931471740973631326608186969523753119546323993892359278563753903149741128282349467136720827132122619177620866305659196267641453819504766216964516467658995724859657544518337771393
N = 61860727516406742636690805639158184396057779906729165734489212939937929906456706343476469874085504076991779041906401043694401076841639925611957258119417559980829238154105119701407722069260962772947894516879731956778127512764229384957918619863998939985369399189275568362193066167855420897196095587732512368673
leak = 23213363443983005040318061737977092634638640953366787443691593387275645092922646169818923792205696350020369122807136306157118385984272980615310163206933078119776935167207473544453080959202803743994251355133953187110546017667004996272367137522351606700447920805532616096125523674597551449412004735397779511371
"""

题目给出了四个输出 num3,ct,N,leak 其中 ct,N 是 RSA 的密文和模数，基本没什么可操作的空间，因此重点就在 num3,leak 上了。

题目还给出了几个关系 $num3 = \frac{num1}{num2}$，其中 $num1>num2$ 且是两个 512 比特的素数；

另外 $leak \equiv (p-q)^{num1} \pmod {num1\cdot num2}$

心路历程

显然我们要从 leak 和 num3 入手。根据 $leak \equiv (p-q)^{num1} \pmod {num1\cdot num2}$，我们有
$$
leak \equiv (p-q)^{num1} \pmod {num1}
$$
由于 num1 是素数，再走一个费马小定理，我们有
$$
leak \equiv p-q \pmod {num1}
$$
因此我们如果能知道 num1 我们就能够得到 $p-q$ 的值（正常来说 $p-q$ 肯定是小于 num1 的，所以直接 $leak \pmod {num1}$ 就会是 $p-q$ 的值了，然后再根据 $N = p\cdot q$，解一个方程组就可以得到 $p,q$ 了，后面就没啥了。

那么现在题目的重点就在于如何根据 $num3 = \frac{num1}{num2}$ 恢复 num1 了。

本地测试

理论上 $\frac{num1}{num2}$ 是一个有理数，由于 num1,num2 都是素数，所以应该也是个无限循环小数。不过虽然这里用的精度已经比较高了 ring = RealField(1100)，但还是没走到它的循环节。不过这么高的精度，应该也能做一些事情了。

尝试通分一下，我们直接使用 sagemath，里头有一个 QQ，代表有理数的类型。例如我们定义 $a=0.25$，直接走一个 $QQ(a)$，就能直接出来 $\frac{1}{4}$

sage: a=0.25
sage: a
0.250000000000000
sage: QQ(a)
1/4

那么我们直接对 num3 应用一下呢？

sage: ring = RealField(1100)
sage: QQ(ring(num3))
27714495913865858197112266003296632001404181823697534106211762432621951228420396951285629763840231667318552711317747751803736439799704150681657112217837660033921787582191772736/22460906974269151983527383579480274910002322616837987158437326900881916880800182097205056972191314686835849128639740399117553858122602145347590837862015308594141255394793343627

好像还挺像那么回事儿的，不过这个分子显然不是一个素数啊。再看到这个分子分母的比特长度

sage: de = 224609069742691519835273835794802749100023226168379871584373269008819
....: 16880800182097205056972191314686835849128639740399117553858122602145347590
....: 837862015308594141255394793343627
sage: de.nbits()
583

也不符合我们 512 比特的预期。想来估计是这点儿误差造成的。怎么办呢？怎么办呢？怎么用一个分数近似地表示一个无限小数呢？而且对分子分母的长度还有一定要求。

不觉得有一个工具非常适配么？连分数哇！还没接触过连分数的读者可以先去我博客的这篇文章看看，当然，网上的资料也已经有很多了。

于是我们直接进行一手对 num3 连分数的算，对收敛分数的取：

from sympy import isprime
num3 = 1.23389923415003373900567515471436168841941584796842188964423737295914869304653496800649965063081353720701415762591488370228399019899893688681309320356016722276295236528757306976510687729729934668311830828756908988350841843676900575414367123810470585198055372776278588638204471298838884740198056387082949710435502826460830711429956
for yx in continued_fraction(num3).convergents():
        y = yx.numerator()
        x = yx.denominator()
        if y.nbits() == 512:
            assert isprime(x) and isprime(y)
            print("[+] ",x,y)
            
            
[+]  9050477566333038464101590216458863799039754468566791821195736389139213194857548339787600682491327798736538059818887575696704421576721592454156775006222517 11167377337790397338811417806698264734026040696284907854286100186126887838302430726803014418419121360514985339992064951270502853852777225947659429837569693

bingo ! 点到为止。

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可联系QQ 643713081，也可以邮件至 643713081@qq.com